home *** CD-ROM | disk | FTP | other *** search
/ Aminet 6 / Aminet 6 - June 1995.iso / Aminet / gfx / 3d / irit50src.lha / irit5 / poly3d-h / out-edge.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-13  |  23.2 KB  |  557 lines

  1. /*****************************************************************************
  2. *   Routines to    test all edges for visibility relative to the global polygon *
  3. * list,    and output the visible ones, to    graphics screen    or as text file         *
  4. *                                         *
  5. * Written by:  Gershon Elber                Ver 2.0, Jan. 1989   *
  6. *****************************************************************************/
  7.  
  8. #include <stdio.h>
  9. #include <math.h>
  10. #include <setjmp.h>
  11. #include <ctype.h>
  12. #include <string.h>
  13. #include "program.h"
  14. #include "genmat.h"
  15.  
  16. #define    MAX_POLYLINE_SIZE    50     /* Maximum size of output polyline. */
  17. #define EDGE_ON_PLANE_EPS    -0.003  /* Epsilon considered edge on plane. */
  18.  
  19. static EdgeStruct *VisOutEdgeHashTable[EDGE_HASH_TABLE_SIZE];
  20. static EdgeStruct *HidOutEdgeHashTable[EDGE_HASH_TABLE_SIZE];
  21.  
  22. static void SaveCurrentMatrix(FILE *OutFile);
  23. static void OutputEdge(EdgeStruct *PEtemp, EdgeStruct *OutEdgeHashTable[]);
  24. static void EmitOutEdgeHashTable(FILE *OutFile,
  25.                  EdgeStruct *OutEdgeHashTable[]);
  26. static char *Real2Str(RealType R);
  27. static EdgeStruct *FoundMatchEdge(int *Colinear,
  28.                   EdgeStruct *PEdge,
  29.                   EdgeStruct *OutEdgeHashTable[]);
  30. static int ColinearPoints(RealType Pt1[3], RealType Pt2[3], RealType Pt3[3]);
  31. static int VisibleEdge(int EdgeMinY,
  32.                EdgeStruct *PEdge,
  33.                IPPolygonStruct *PolyHashTbl[]);
  34. static int VisiblePointOnePoly(RealType MidPt[3], IPPolygonStruct *PPoly);
  35. static int ZCrossProd(RealType Pt1[3], RealType Pt2[3], RealType Pt3[3]);
  36.  
  37. /*****************************************************************************
  38. * DESCRIPTION:                                                               M
  39. * Routine to test for visibility all edges in EdgeHashTable and    display    or   M
  40. * output the visible ones only.    It is assumed that only    totally    visible    or   M
  41. * invisible edges are in table (Pass 3 broke all other kind of edges).         M
  42. *   Hidden information will also be dumped out with hidden attributes if     M
  43. * GlblOutputHiddenData is TRUE.                                              M
  44. *                                                                            *
  45. * PARAMETERS:                                                                M
  46. *   OutFile:     Where output should go to.                                  M
  47. *                                                                            *
  48. * RETURN VALUE:                                                              M
  49. *   void                                                                     M
  50. *                                                                            *
  51. * KEYWORDS:                                                                  M
  52. *   OutVisibleEdges, visibility                                              M
  53. *****************************************************************************/
  54. void OutVisibleEdges(FILE *OutFile)
  55. {
  56.     int    i;
  57.     EdgeStruct *PEtemp, *PEtail;
  58.  
  59.     IritCPUTime(TRUE);
  60.  
  61.     if (!GlblQuiet)
  62.     fprintf(stderr, "\nPass 4, Edges [%5d] =      ", EdgeCount);
  63.     for (i = 0; i < EDGE_HASH_TABLE_SIZE; i++)
  64.     VisOutEdgeHashTable[i] = HidOutEdgeHashTable[i] = NULL;
  65.  
  66.     if (!MatInverseMatrix(GlblViewMat, GlblViewMat)) {
  67.     fprintf(stderr,
  68.             "\nNo inverse for matrix transformation, output is in screen space\n");
  69.     MatGenUnitMat(GlblViewMat);         /* No inverse transform at all. */
  70.     }
  71.  
  72.     IRIT_DATA_HEADER(OutFile, "Poly3d-h");
  73.  
  74.     EdgeCount =    0;
  75.  
  76.     /* Output the viewing matrices. */
  77.     SaveCurrentMatrix(OutFile);
  78.  
  79.     for (i = 0; i < EDGE_HASH_TABLE_SIZE; i++)
  80.     if ((PEtemp = EdgeHashTable[i]) != NULL)/* If any edge in that list. */
  81.         while (PEtemp) {
  82.         EdgeCount++;
  83.         if (!GlblQuiet)
  84.             fprintf(stderr, "\b\b\b\b\b%5d", EdgeCount);
  85.         PEtail = PEtemp    -> Pnext;       /* OutputEdge destroy it. */
  86.         if ((!PEtemp -> Internal || GlblInternal))
  87.             if (VisibleEdge(i, PEtemp, PolyHashTable))
  88.             OutputEdge(PEtemp, VisOutEdgeHashTable);
  89.             else if (GlblOutputHiddenData)
  90.             OutputEdge(PEtemp, HidOutEdgeHashTable);
  91.         PEtemp = PEtail;
  92.         }
  93.  
  94.  
  95.     /* Output the visible data: */
  96.     if (GlblOutputHasRGB) {
  97.     fprintf(OutFile,
  98.         "[OBJECT [COLOR %d] [RGB %d,%d,%d] [WIDTH %8.6f] Visible\n",
  99.         GlblOutputColor,
  100.         GlblOutputRGB[0], GlblOutputRGB[1], GlblOutputRGB[2],
  101.         GlblOutputWidth);
  102.     }
  103.     else {
  104.     fprintf(OutFile, "[OBJECT [COLOR %d] [WIDTH %8.6f] Visible\n",
  105.         GlblOutputColor, GlblOutputWidth);
  106.     }
  107.     /* Output all visible data. */
  108.     EmitOutEdgeHashTable(OutFile, VisOutEdgeHashTable);
  109.     fprintf(OutFile, "]\n\n");
  110.  
  111.     /* Output the hidden data if requested: */
  112.     if (GlblOutputHiddenData) {
  113.     if (GlblOutputHasRGB) {
  114.         fprintf(OutFile, "[OBJECT [HIDDEN] [COLOR %d] [RGB %d,%d,%d] [WIDTH %8.6f] Hidden\n",
  115.             HIDDEN_COLOR,
  116.             GlblOutputRGB[0] / HIDDEN_COLOR_RATIO,
  117.             GlblOutputRGB[1] / HIDDEN_COLOR_RATIO,
  118.             GlblOutputRGB[2] / HIDDEN_COLOR_RATIO,
  119.             GlblOutputWidth / HIDDEN_WIDTH_RATIO);
  120.     }
  121.     else {
  122.         fprintf(OutFile, "[OBJECT [HIDDEN] [COLOR %d] [WIDTH %8.6f] Hidden\n",
  123.             HIDDEN_COLOR, GlblOutputWidth / HIDDEN_WIDTH_RATIO);
  124.     }
  125.     /* Output all hidden data. */
  126.     EmitOutEdgeHashTable(OutFile, HidOutEdgeHashTable);
  127.     fprintf(OutFile, "]\n\n");
  128.     }
  129.  
  130.     if (!GlblQuiet)
  131.     fprintf(stderr, ",  %6.2f seconds.", IritCPUTime(FALSE));
  132. }
  133.  
  134. /*****************************************************************************
  135. * DESCRIPTION:                                                               *
  136. * Saves current view transformation.                                         *
  137. *                                                                            *
  138. * PARAMETERS:                                                                *
  139. *   OutFile:     Where output should go to.                                  *
  140. *                                                                            *
  141. * RETURN VALUE:                                                              *
  142. *   void                                                                     *
  143. *****************************************************************************/
  144. static void SaveCurrentMatrix(FILE *OutFile)
  145. {
  146.     int    i, j;
  147.  
  148.     fprintf(OutFile, "[OBJECT MATRICES\n    [OBJECT VIEW_MAT\n\t[MATRIX");
  149.     for (i = 0; i < 4; i++) {
  150.     fprintf(OutFile, "\n\t    ");
  151.     for (j = 0; j < 4; j++)
  152.         fprintf(OutFile, "%12f ", IritPrsrViewMat[i][j]);
  153.     }
  154.     fprintf(OutFile, "\n\t]\n    ]\n");
  155.  
  156.     if (IritPrsrWasPrspMat) {
  157.     fprintf(OutFile, "    [OBJECT PRSP_MAT\n\t[MATRIX");
  158.     for (i = 0; i < 4; i++) {
  159.         fprintf(OutFile, "\n\t    ");
  160.         for (j = 0; j < 4; j++)
  161.         fprintf(OutFile, "%12f ", IritPrsrPrspMat[i][j]);
  162.     }
  163.     fprintf(OutFile, "\n\t]\n    ]\n");
  164.     }
  165.  
  166.     fprintf(OutFile, "]\n\n");
  167. }
  168.  
  169. /*****************************************************************************
  170. * DESCRIPTION:                                                               *
  171. * Routine to output one    edge to    the OutEdgeHashTable.                 *
  172. *   The edge is inserted into OutEdgeHashTable to be able to match it into   *
  173. * the longest path possible - connecting edges into edge sequence.         *
  174. *   Each edge is inserted by its Ymin, which will cause the paths be in         *
  175. * increased Y order...                                 *
  176. *                                                                            *
  177. * PARAMETERS:                                                                *
  178. *   PEtemp:           Edge to insert into hash table.                        *
  179. *   OutEdgeHashTable: The hash table to put PEtemp in.                       *
  180. *                                                                            *
  181. * RETURN VALUE:                                                              *
  182. *   void                                                                     *
  183. *****************************************************************************/
  184. static void OutputEdge(EdgeStruct *PEtemp, EdgeStruct *OutEdgeHashTable[])
  185. {
  186.     int    Level;
  187.  
  188.     Level = (int) ((PEtemp -> Vertex[0]    -> Coord[1] + 1.0) *
  189.                             EDGE_HASH_TABLE_SIZE2);
  190.     Level = BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1);
  191.     PEtemp -> Pnext = OutEdgeHashTable[Level];
  192.     OutEdgeHashTable[Level] = PEtemp;
  193. }
  194.  
  195. /*****************************************************************************
  196. * DESCRIPTION:                                                               *
  197. * Routine to scan the OutEdgeHashTable,    and Emit the longest paths found in  *
  198. * it by    searching for consecutive edges    and combining colinear edges.         *
  199. *                                                                            *
  200. * PARAMETERS:                                                                *
  201. *   OutFile:            Where output should go to.                           *
  202. *   OutEdgeHashTable:   Hash table to scan.                                  *
  203. *                                                                            *
  204. * RETURN VALUE:                                                              *
  205. *   void                                                                     *
  206. *****************************************************************************/
  207. static void EmitOutEdgeHashTable(FILE *OutFile, EdgeStruct *OutEdgeHashTable[])
  208. {
  209.     int    i, j, Colinear, Count;
  210.     RealType Vec[MAX_POLYLINE_SIZE][3];
  211.     EdgeStruct *PEtemp, *PEnext;
  212.  
  213.     for    (i = 0; i < EDGE_HASH_TABLE_SIZE; i++)     /* Scan all the hash table. */
  214.     while (OutEdgeHashTable[i]) {         /* Scan all edges in entry. */
  215.         PEtemp = OutEdgeHashTable[i];      /* Take edge out of table. */
  216.         OutEdgeHashTable[i]    = OutEdgeHashTable[i] -> Pnext;
  217.  
  218.         /* Print first vertices of polyline: */
  219.         Count = 0;
  220.         MatMultVecby4by4(Vec[Count++], PEtemp -> Vertex[0] -> Coord,
  221.                                 GlblViewMat);
  222.         MatMultVecby4by4(Vec[Count++], PEtemp -> Vertex[1] -> Coord,
  223.                                 GlblViewMat);
  224.  
  225.         while ((PEnext = FoundMatchEdge(&Colinear, PEtemp,
  226.                         OutEdgeHashTable)) != NULL) {
  227.         if (Colinear)                /* Overwrite last entry. */
  228.             MatMultVecby4by4(Vec[Count - 1],
  229.                      PEnext -> Vertex[1] -> Coord,
  230.                      GlblViewMat);
  231.         else
  232.             MatMultVecby4by4(Vec[Count++],
  233.                      PEnext -> Vertex[1] -> Coord,
  234.                      GlblViewMat);
  235.         if (Count >= MAX_POLYLINE_SIZE)
  236.             break;
  237.         PEtemp = PEnext;
  238.         }
  239.  
  240.         fprintf(OutFile, "    [POLYLINE %d\n", Count);
  241.         for (j = 0; j < Count; j++)
  242.         fprintf(OutFile, "\t[%s %s %s]\n",
  243.             Real2Str(Vec[j][0]),
  244.             Real2Str(Vec[j][1]),
  245.             Real2Str(Vec[j][2]));
  246.  
  247.         fprintf(OutFile, "    ]\n");
  248.     }
  249. }
  250.  
  251. /*****************************************************************************
  252. * DESCRIPTION:                                                               *
  253. * Converts a real number into a string.                         *
  254. *   The routine maintains 3 different buffers simultanuously so up to 3      *
  255. * calls can be issued from same printf...                     *
  256. *                                                                            *
  257. * PARAMETERS:                                                                *
  258. *   R:         To convert to a string.                                       *
  259. *                                                                            *
  260. * RETURN VALUE:                                                              *
  261. *   char *:    A string representation for R.                                *
  262. *****************************************************************************/
  263. static char *Real2Str(RealType R)
  264. {
  265.     static int i = 0;
  266.     static char Buffer[3][LINE_LEN_LONG];
  267.     int j, k;
  268.  
  269.     if (ABS(R) < 1e-6)
  270.     R = 0.0;            /* Round off very small numbers. */
  271.  
  272.     sprintf(Buffer[i], "%-8.6g", R);
  273.  
  274.     for (k = 0; !isdigit(Buffer[i][k]) && k < LINE_LEN_LONG; k++);
  275.     if (k >= LINE_LEN_LONG) {
  276.     fprintf(stderr, "Conversion of real number failed.\n");
  277.     Poly3dhExit(3);
  278.     }
  279.  
  280.     for (j = strlen(Buffer[i]) - 1; Buffer[i][j] == ' ' && j > k; j--);
  281.     if (strchr(Buffer[i], '.') != NULL)
  282.     for (; Buffer[i][j] == '0' && j > k; j--);
  283.     Buffer[i][j+1] = 0;
  284.  
  285.     j = i;
  286.     i = (i + 1) % 3;
  287.     return Buffer[j];
  288. }
  289.  
  290. /*****************************************************************************
  291. * DESCRIPTION:                                                               *
  292. * Routine to scan the OutEdgeHashTable for a match edge    if any,    delete it    *
  293. * from HashTable and return it.                             *
  294. *   If colinear with PEdge sets Colinear to TRUE.                 *
  295. *   Returns NULL if no match found (end of polyline).                 *
  296. *                                                                            *
  297. * PARAMETERS:                                                                *
  298. *   Colinear:         Is this edge collinear with PEdge?                     *
  299. *   PEdge:            To search for a match.                                 *
  300. *   OutEdgeHashTable: Hash teable to searc.                                  *
  301. *                                                                            *
  302. * RETURN VALUE:                                                              *
  303. *   EdgeStruct *:     Matched edge, or NULL if none found.                   *
  304. *****************************************************************************/
  305. static EdgeStruct *FoundMatchEdge(int *Colinear,
  306.                   EdgeStruct *PEdge,
  307.                   EdgeStruct *OutEdgeHashTable[])
  308. {
  309.     int    Level;
  310.     EdgeStruct *PEtemp, *PElast;
  311.  
  312.     Level = (int) ((PEdge -> Vertex[1] -> Coord[1] + 1.0) *
  313.                             EDGE_HASH_TABLE_SIZE2);
  314.     Level = BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1);
  315.     PEtemp = PElast = OutEdgeHashTable[Level];
  316.     while (PEtemp) {                /* First scan for colinear edge. */
  317.     if (PT_APX_EQ(PEdge -> Vertex[1] -> Coord,
  318.               PEtemp -> Vertex[0] -> Coord) &&
  319.         ColinearPoints(PEdge -> Vertex[0] -> Coord,
  320.                PEdge -> Vertex[1] -> Coord,
  321.                PEtemp -> Vertex[1] -> Coord)) {
  322.         *Colinear =    TRUE;
  323.         /* Delete that edge    from hash table    structure: */
  324.         if (PEtemp == PElast)
  325.         OutEdgeHashTable[Level] = OutEdgeHashTable[Level] -> Pnext;
  326.         else
  327.         PElast -> Pnext = PEtemp -> Pnext;
  328.  
  329.         if (PT_APX_EQ(PEtemp -> Vertex[0] -> Coord,
  330.               PEtemp -> Vertex[1] -> Coord))
  331.         return FoundMatchEdge(Colinear, PEdge, OutEdgeHashTable);
  332.         else
  333.             return PEtemp;
  334.     }
  335.     PElast = PEtemp;
  336.     PEtemp = PEtemp    -> Pnext;
  337.     }
  338.  
  339.     PEtemp = PElast = OutEdgeHashTable[Level];
  340.     while (PEtemp) {                /* Next scan for any match edge. */
  341.     if (PT_APX_EQ(PEdge -> Vertex[1] -> Coord,
  342.               PEtemp -> Vertex[0] -> Coord)) {
  343.         *Colinear =    FALSE;
  344.         /* Delete that edge    from hash table    structure: */
  345.         if (PEtemp == PElast)
  346.         OutEdgeHashTable[Level] = OutEdgeHashTable[Level] -> Pnext;
  347.         else
  348.             PElast -> Pnext = PEtemp -> Pnext;
  349.  
  350.         if (PT_APX_EQ(PEtemp -> Vertex[0] -> Coord,
  351.               PEtemp -> Vertex[1] -> Coord))
  352.         return FoundMatchEdge(Colinear, PEdge, OutEdgeHashTable);
  353.         else
  354.         return PEtemp;
  355.     }
  356.     PElast = PEtemp;
  357.     PEtemp = PEtemp    -> Pnext;
  358.     }
  359.  
  360.     return NULL;                  /* No match - end of polyline. */
  361. }
  362.  
  363. /*****************************************************************************
  364. * DESCRIPTION:                                                               *
  365. * Routine to test if three points are colinear.                     *
  366. *   Algorithm: cross product should be zero if colinear...             *
  367. *   Note this routine does not return TRUE if Pt2 is not between Pt1..Pt3.   *
  368. *                                                                            *
  369. * PARAMETERS:                                                                *
  370. *   Pt1, Pt2, Pt3:  The three points to test for colinearity.                *
  371. *                                                                            *
  372. * RETURN VALUE:                                                              *
  373. *   int:        TRUE if colinear, FALSE otherwise.                           *
  374. *****************************************************************************/
  375. static int ColinearPoints(RealType Pt1[3], RealType Pt2[3], RealType Pt3[3])
  376. {
  377.     int    i;
  378.     RealType Xout, Yout, Zout, U[3], V[3], temp;
  379.  
  380.     for    (i = 0; i < 3; i++) {
  381.     U[i] = Pt2[i] -    Pt1[i];
  382.     V[i] = Pt3[i] -    Pt2[i];
  383.     }
  384.     temp = sqrt(SQR(U[0]) + SQR(U[1]) + SQR(U[2]));
  385.     if (APX_EQ(temp, 0.0))
  386.     return TRUE;
  387.     for    (i = 0; i < 3; i++)
  388.     U[i] = U[i] / temp;
  389.  
  390.     temp = sqrt(SQR(V[0]) + SQR(V[1]) + SQR(V[2]));
  391.     if (APX_EQ(temp, 0.0))
  392.     return TRUE;
  393.     for    (i = 0; i < 3; i++)
  394.     V[i] = V[i] / temp;
  395.  
  396.     /* Xoutput = Uy * Vz - Uz *    Vy. */
  397.     Xout = U[1]    /* Uy */  * V[2] /* Vz */  -
  398.        U[2]    /* Uz */  * V[1] /* Vy */;
  399.  
  400.     /* Youtput = Uz * Vx - Ux *    Vz. */
  401.     Yout = U[2]    /* Uz */  * V[0] /* Vx */  -
  402.        U[0]    /* Ux */  * V[2] /* Vz */;
  403.  
  404.     /* Zoutput = Ux * Vy - Uy *    Vx. */
  405.     Zout = U[0]    /* Ux */  * V[1] /* Vy */  -
  406.        U[1]    /* Uy */  * V[0] /* Vx */;
  407.  
  408.     return APX_EQ(Xout, 0.0) && APX_EQ(Yout, 0.0) && APX_EQ(Zout, 0.0) &&
  409.        ((MIN(Pt1[0], Pt3[0]) < Pt2[0]) && (MAX(Pt1[0], Pt3[0]) > Pt2[0]) &&
  410.         (MIN(Pt1[1], Pt3[1]) < Pt2[1]) && (MAX(Pt1[1], Pt3[1]) > Pt2[1]));
  411. }
  412.  
  413. /*****************************************************************************
  414. * DESCRIPTION:                                                               *
  415. * Routine to test the visibility of the    given edge relative to all polygons  *
  416. * in polygon list. Return TRUE if the edge is visible. It is assumed that    *
  417. * the edge is whole visible or whole invisible (Pass 3 broke the edge if     *
  418. * that whas not    true). Also it is assumed the polygons are all convex.         *
  419. *   A short cut is made to test the edge only against the needed polygons    *
  420. * only, using the polygon hash table and Y level sorting.             *
  421. *                                                                            *
  422. * PARAMETERS:                                                                *
  423. *   EdgeMinY:      Index into the hash table of polygons.                    *
  424. *   PEdge:         Edge to examine its visibility.                           *
  425. *   PolyHashTbl:   Hash table of polygons.                                   *
  426. *                                                                            *
  427. * RETURN VALUE:                                                              *
  428. *   int:           TRUE if visible, FALSE otherwise.                         *
  429. *****************************************************************************/
  430. static int VisibleEdge(int EdgeMinY,
  431.                EdgeStruct *PEdge,
  432.                IPPolygonStruct *PolyHashTbl[])
  433. {
  434.     int    EdgeMaxY, i;
  435.     RealType MidPt[3];
  436.     IPPolygonStruct *PPolyList, *PPolyLast;
  437.  
  438.     EdgeMaxY = (int) (MIN((MAX(PEdge -> Vertex[0] -> Coord[1],
  439.                    PEdge -> Vertex[1] -> Coord[1]) + 1.0) *
  440.                         EDGE_HASH_TABLE_SIZE2,
  441.               EDGE_HASH_TABLE_SIZE1));
  442.  
  443.     for    (i = 0; i < 3; i++)            /* Calc a mid point on the edge: */
  444.     MidPt[i] = (PEdge -> Vertex[0] -> Coord[i] +
  445.             PEdge -> Vertex[1] -> Coord[i]) / 2.0;
  446.     MidPt[2] -= EDGE_ON_PLANE_EPS * 3;
  447.  
  448.     /* Test the    edge only in the interval 0..EdgeMaxY as these are the only  */
  449.     /* which might hide    that edge. Also    polygons with MaxY less    than         */
  450.     /* EdgeMinY    are deleted from PolyHashTbl as it is assumed the edges      */
  451.     /* are scanned in increasing order of the EdgeHashTable.             */
  452.     for    (i = 0; i <= EdgeMaxY; i++) {
  453.     PPolyList = PPolyLast =    PolyHashTbl[i];
  454.     while (PPolyList) {
  455.         if ((PPolyList -> BBox[1][1] + 1.0) *
  456.                           EDGE_HASH_TABLE_SIZE2 < EdgeMinY)
  457.         /* Delete this polygon!    */
  458.         if (PPolyList == PPolyLast) {
  459.             PolyHashTbl[i] = PPolyLast = PPolyList -> Pnext;
  460.             PPolyList =    PPolyList -> Pnext;
  461.         }
  462.         else {
  463.             PPolyList =    PPolyList -> Pnext;
  464.             PPolyLast -> Pnext = PPolyList;
  465.         }
  466.         else {         /* Polygon still active - test edge against it. */
  467.         /* If found one    polygon    that hides this    edge return FALSE... */
  468.  
  469.         if (!VisiblePointOnePoly(MidPt, PPolyList))
  470.             return FALSE;
  471.         PPolyLast = PPolyList;
  472.         PPolyList = PPolyList -> Pnext;
  473.         }
  474.     }
  475.     }
  476.  
  477.     return TRUE;
  478. }
  479.  
  480. /*****************************************************************************
  481. * DESCRIPTION:                                                               *
  482. * Routine to test the visibility of the    given edge relative to one polygon   *
  483. * by testing a single point on the polygon.                     *
  484. *   Returns TRUE if the edge is visible. It is assumed that the edge is      *
  485. * completely visible or completely invisible (Pass 3 broke the edge if that  *
  486. * was not true).                                 *
  487. *   Also it is assumed the polygons are all convex.                 *
  488. *                                                                            *
  489. * PARAMETERS:                                                                *
  490. *   MidPt:     A middle point on the examined edge,for visibility testing.   *
  491. *   PPoly:     List of polygons to verify MidPt's visibility against.        *
  492. *                                                                            *
  493. * RETURN VALUE:                                                              *
  494. *   int:       TRUE if visible, FALSE otherwise.                             *
  495. *****************************************************************************/
  496. static int VisiblePointOnePoly(RealType MidPt[3], IPPolygonStruct *PPoly)
  497. {
  498.     IPVertexStruct *PList;
  499.  
  500.     /* Test if edges is    out of polygon boundary    box: */
  501.     if (MidPt[0] > PPoly -> BBox[1][0] || MidPt[0] < PPoly -> BBox[0][0] ||
  502.     MidPt[1] > PPoly -> BBox[1][1] || MidPt[1] < PPoly -> BBox[0][1])
  503.     return TRUE;
  504.  
  505.     if (PPoly -> Plane[0] * MidPt[0] +
  506.     PPoly -> Plane[1] * MidPt[1] +
  507.     PPoly -> Plane[2] * MidPt[2] +
  508.     PPoly -> Plane[3] > EDGE_ON_PLANE_EPS)
  509.     return TRUE;                /* Edge in front of polygon. */
  510.  
  511.     /* We cannt    escape it - we now must    find if    the point is included in */
  512.     /* polygon area. We    assume the polygon is convex and use the fact     */
  513.     /* that the    polygon    list is    ordered    such that the cross product     */
  514.     /* of two consecutive vertices and the point is positive for all     */
  515.     /* consecutive vertices pairs iff the point    is in the polygon.     */
  516.     PList = PPoly -> PVertex;
  517.     while (PList -> Pnext) {
  518.     if (ZCrossProd(PList -> Coord, PList -> Pnext -> Coord, MidPt) < 0)
  519.         return TRUE;                  /* Out of polygon! */
  520.     PList =    PList -> Pnext;
  521.     }
  522.     /* Now test    last polygon edge (last    point, first point in poly list) */
  523.     if (ZCrossProd(PList -> Coord, PPoly -> PVertex -> Coord, MidPt) < 0)
  524.     return TRUE;                      /* Out of polygon! */
  525.  
  526.     return FALSE;
  527. }
  528.  
  529. /*****************************************************************************
  530. * DESCRIPTION:                                                               M
  531. * Routine to evaluate the cross    product    of 3 points projected to Z = 0 plane M
  532. * and return the sign of the result (Only Z component).                 M
  533. *                                                                            *
  534. * PARAMETERS:                                                                M
  535. *   Pt1, Pt2, Pt3:  Three points to compute Z component of cross product.    M
  536. *                                                                            *
  537. * RETURN VALUE:                                                              M
  538. *   int:        Sign of Z component of cross product.                        M
  539. *                                                                            *
  540. * KEYWORDS:                                                                  M
  541. *   ZCrossProd                                                               M
  542. *****************************************************************************/
  543. static int ZCrossProd(RealType Pt1[3], RealType Pt2[3], RealType Pt3[3])
  544. {
  545.     RealType Zout;
  546.  
  547.     /* U = Pt2 - Pt1,  V = Pt3 - Pt2,        Zoutput    = Ux * Vy - Uy * Vx. */
  548.     Zout = (Pt2[0] - Pt1[0]) /*    Ux */  * (Pt3[1] - Pt2[1]) /* Vy */  -
  549.        (Pt2[1] - Pt1[1]) /*    Uy */  * (Pt3[0] - Pt2[0]) /* Vx */;
  550.     if (APX_EQ(Zout, 0.0))
  551.     return 0;
  552.     if (Zout < 0.0)
  553.     return -1;
  554.     else
  555.     return 1;
  556. }
  557.